package com.mdnote.structure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/6
 * @description 广度优先搜索算法
 */
public class BroadFirstSearch {


    private List<String> vertexList;

    private int[][] edges;

    private int numOfEdge;

    private boolean[] isVisited;

    public BroadFirstSearch(int size) {
        this.vertexList = new ArrayList<>(size);
        this.edges = new int[size][size];
        this.numOfEdge = 0;
        this.isVisited = new boolean[size];
    }

    public void insertVertex(String vertex) {
        this.vertexList.add(vertex);
    }

    public void addEdge(int v1Index, int v2Index, int weight) {
        this.edges[v1Index][v2Index] = weight;
        this.edges[v2Index][v1Index] = weight;
        this.numOfEdge++;
    }

    public int vertexSize() {
        return this.vertexList.size();
    }

    public int edgeNum() {
        return this.numOfEdge;
    }

    public void showEdges() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 是否已经访问
     * @param index 索引
     * @return 是否访问过
     */
    private boolean isVisited(int index) {
        return this.isVisited[index];
    }

    /**
     * 找到第一个连接的元素
     * @param vertexIndex 某个顶点
     * @return 第一个相邻元素的索引
     */
    private int getFirstNeighbor(int vertexIndex) {
        for (int i = 0; i < edges.length; i++) {
            if (this.edges[vertexIndex][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 找到下一个相连的元素
     * @param vertexIndex 顶点
     * @param preVertex 上一个连接点的索引
     * @return 下一个连接点的索引
     */
    private int getNextVertex(int vertexIndex, int preVertex) {
        for (int i = preVertex + 1; i < edges.length; i++) {
            if (this.edges[vertexIndex][i] > 0) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 广度优先搜索
     * @param isVisited 访问记录
     * @param index 当前元素
     */
    public void bfs(boolean[] isVisited, int index) {
        // 创建一个队列用于暂存元素
        LinkedList<Integer> queue = new LinkedList<>();
        // 保存当前指向的顶点
        int u = 0;
        // 与u顶点相连的顶点
        int i = 0;
        // 先处理第一个元素
        isVisited[index] = true;
        queue.addLast(index);
        System.out.print(vertexList.get(index) + " ");

        while (!queue.isEmpty()) {
            // 以队列头部的元素为顶点
            u = queue.removeFirst();
            // 找到第一个元素
            i = getFirstNeighbor(u);

            while (i != -1) {
                // 跳过成环的元素
                if (!isVisited(i)) {
                    isVisited[i] = true;
                    queue.addLast(i);
                    System.out.print(vertexList.get(i) + " ");
                }
                i = getNextVertex(u, i);
            }
        }
    }

    /**
     * 广度优先搜索
     */
    private void bfs() {
        for (int i = 0; i < this.vertexList.size(); i++) {
            if (!isVisited(i)) {
                bfs(this.isVisited, i);
            }
        }
    }


    public static void main(String[] args) {
        String[] strs = new String[]{"A", "B", "C", "D", "E"};
        BroadFirstSearch depthFirstSearch = new BroadFirstSearch(strs.length);
        for (String str : strs) {
            depthFirstSearch.insertVertex(str);
        }

        depthFirstSearch.addEdge(0, 1, 1);
        depthFirstSearch.addEdge(0, 2, 1);
        depthFirstSearch.addEdge(1, 2, 1);
        depthFirstSearch.addEdge(1, 3, 1);
        depthFirstSearch.addEdge(1, 4, 1);

        depthFirstSearch.showEdges();

        depthFirstSearch.bfs();

    }

}
